package com.lw.leetcode.tree.b;

/**
 * Created with IntelliJ IDEA.
 * 211. 添加与搜索单词 - 数据结构设计
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/19 9:08
 */
public class WordDictionary {


    public static void main(String[] args) {

        WordDictionary test = new WordDictionary();
        boolean search = true;

        // true   true   false
//        test.addWord("abc");
//        test.addWord("efd");
//        search = test.search("abc");
//        System.out.print(search + "   ");
//        search = test.search(".bc");
//        System.out.print(search + "   ");
//        search = test.search(".be");
//        System.out.print(search + "   ");
//        System.out.println();

        // true   true   true   false   true   false   true   true
        test.addWord("a");
        test.addWord("ab");
        search = test.search("a");
        System.out.print(search + "   ");
        search = test.search("a.");
        System.out.print(search + "   ");
        search = test.search("ab");
        System.out.print(search + "   ");
        search = test.search(".a");
        System.out.print(search + "   ");
        search = test.search(".b");
        System.out.print(search + "   ");
        search = test.search("ab.");
        System.out.print(search + "   ");
        search = test.search(".");
        System.out.print(search + "   ");
        search = test.search("..");
        System.out.print(search + "   ");
        System.out.println();

        //

        // ["WordDictionary","addWord","addWord","addWord","addWord","addWord","addWord","addWord","addWord","search","search","search","search","search","search","search","search","search","search"]
        //[[],["ran"],["rune"],["runner"],["runs"],["add"],["adds"],["adder"],["addee"],
        // ["r.n"],["ru.n.e"],["add"],["add."],["adde."],[".an."],["...s"],["....e."],["......."],["..n.r"]]
        //输出：
        //[null,null,null,null,null,null,null,null,null,true,false,true,false,true,false,true,true,false,false]
        //预期结果：
        //[null,null,null,null,null,null,null,null,null,true,false,true,true,true,false,true,true,false,false]


        test.addWord("ran");
        test.addWord("rune");
        test.addWord("runner");
        test.addWord("runs");
        test.addWord("add");
        test.addWord("adds");
        test.addWord("adder");
        test.addWord("addee");
        search = test.search("add.");
        System.out.print(search + "   ");
        search = test.search("a.");
        System.out.print(search + "   ");
        search = test.search("ab");
        System.out.print(search + "   ");
        search = test.search(".a");
        System.out.print(search + "   ");
        search = test.search(".b");
        System.out.print(search + "   ");
        search = test.search("ab.");
        System.out.print(search + "   ");
        search = test.search(".");
        System.out.print(search + "   ");
        search = test.search("..");
        System.out.print(search + "   ");
    }


    private Tree[] roots;

    public WordDictionary() {
        roots = new Tree[26];
    }

    public void addWord(String word) {
        char[] chars = word.toCharArray();
        find(roots, chars, 0);
    }

    private void find(Tree[] nodes, char[] chars, int index) {
        char aChar = chars[index];
        Tree node = nodes[aChar - 'a'];
        if (node == null) {
            node = new Tree();
            nodes[aChar - 'a'] = node;
        }
        node.have = true;
        if (index == chars.length - 1) {
            node.end = true;
            return;
        }
        find(node.nexts, chars, index + 1);
    }

    public boolean search(String word) {
        char[] chars = word.toCharArray();
        return f(roots, chars, 0);
    }

    private boolean f(Tree[] nodes, char[] chars, int index) {

        char c = chars[index];
        if (c == '.') {
            for (Tree node : nodes) {
                if (node != null && node.have) {
                    if (node.end && chars.length - 1 == index) {
                        return true;
                    }
                    if (chars.length - 1 == index) {
                        continue;
                    }
                    boolean f = f(node.nexts, chars, index + 1);
                    if (f) {
                        return true;
                    }
                }
            }
            return false;
        } else {
            Tree node = nodes[c - 'a'];
            if (node != null && node.have) {
                if (node.end && chars.length - 1 == index) {
                    return true;
                }
                if (chars.length - 1 == index) {
                    return false;
                }
                return f(node.nexts, chars, index + 1);
            }
            return false;
        }
    }

    private class Tree {
        private boolean have;
        private boolean end;
        private Tree[] nexts = new Tree[26];
    }

}
